計算可能性 (computability)

計算論理 Computational logic - Wikipedia ではない。これは論理を計算する事を硏究する

計算模型

λ計算 (lambda caliculus)

μ再歸函數 (μ-recursive function。歸納的函數 (recursive function))

集合$ Xは以下を滿たすならば歸納的集合 (R)である

$ \varnothing\in X

$ x\in Xならば$ x\cup\{x\}\in X

歸納言語 (R) (recursive language。Turing-decidable language)

文字列が歸納言語に屬するか否かを萬能 Turing 機械で判定できる

歸納的可算集合 (RE) (recursively enumerable set。計算可枚擧集合 (computably enumerable set)。半決定可能集合 (semidecidable set)。證明可能集合。Turing-認識可能集合)

$ \sf RE (recursively enumerable)

歸納的可算言語 (RE) (recursively enumerable language。部分決定性言語 (partially decidable language)。Turing 受理性言語 (Turing-recognizable language))

文字列が言語に含まれてゐれば萬能 Turing 機械はその文字列を受理し停止する

combinatory 論理 (combinatory logic)

項書き換へ (term rewriting)

これは表現ってやつでは???